{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 随机梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "m = 100000\n",
    "\n",
    "x = np.random.normal(size=m)\n",
    "X = x.reshape(-1,1)\n",
    "y = 4.*x + 3. + np.random.normal(0, 3, size=m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X+QHOV5J/DvM7MtaUbkmFWQHTRokeLiRKFTYIstrNT+\nESM7ks8yYgMBwuGUU/cH/yRVEaXbu+VMkKgiYatUNqQqqbrjklScgsMSBg8icqKzLa6uokTYK8+u\nlbXRGQyWGHBQjIYE7SDNzr75Y6ZHPT3dPd0z3dO/vp8qCu3s7My7s7vPvP28z/u8opQCERElXybs\nARAR0XAw4BMRpQQDPhFRSjDgExGlBAM+EVFKMOATEaUEAz4RUUow4BMRpQQDPhFRSoyEPQCja665\nRm3atCnsYRARxcqpU6f+WSm1vtf9IhXwN23ahLm5ubCHQUQUKyLyUzf3Y0qHiCglGPCJiFKCAZ+I\nKCUY8ImIUoIBn4goJSJVpUNEFAWlcgUHj53BO9UaNhRymN61BVPjxbCHNTAGfCIig1K5godfPI1a\nvQEAqFRrePjF0wAQ+6DPlA4RkcHBY2fawV5Xqzdw8NiZkEbkHwZ8IiKDd6o1T7fHCQM+EZHBhkLO\n0+1xwoBPRGQwvWsLclq247aclsX0ri0hjcg/XLQlIkJnZU4hr2H1SAYf1Oqs0iEi8lPYZZDmypwL\nS3XktCyevO+WRAR6HQM+EYXKSxmk/sZQqdaQFUFDKRQ9vEHYvbE4VeYw4BMR+cRtsDW/MTSUAtB8\ng5j++gIA5zp5pzeWMCtzhnl1w4BPRENnDHLK5j6Vag2Ts8fbgfDipeWuNwZdvaHw2MuLjoHS6Y1l\nQyGHikVwD7oyZ9ibvFilQ0RDpQe5ikOwBwAB2vepVGuo1uqOj3thyfnzTrP4sCpzhr3JiwGfiCyV\nyhVMzh7H5pmjmJw9jlK54svjWgU5K05vBv0o5DXL2zcUcpgaL+KJu7ahWMhBABRyGtZoGTx0aN7X\n791s2KkkBnwi6mKeheupBj8CX5B5cbvxlcoVfGBzBXD7jc2jYKfGizgxswNP3ncLLi2v4MJS3ffv\n3WzYm7yYwyeiLkFWrdjly/Wqm0HYje/gsTNYsfma5149h2dPnm0vmNp97/sOL3Q8nh+LrNO7tnTk\n8IFgU0kM+ETUJchUg1WQE2DgYA9Yj69Urli+weiM1T7mcZnvN/38AiDNRWLj1wD9LbLqX8MqHSIK\nTdBVKyum4O5Xvt48Pj015VavtYX6SvdIB73ymRovDq3Wf+CALyIbAfwVgI+j+XN7Win1xyKyDsAh\nAJsAvAXgXqXUhUGfj4iC52eqwdyy4INaHRZxc2DG8Rk3aA1DXDpp+jHDXwawTyn1fRH5BQCnRORb\nAH4HwHeUUrMiMgNgBsB/8+H5iChg/aYaHimdxnOvnkNDKWRF8Mvr83j9vYvtGXyv0km3BJ1XBaN5\nDfvv2Iqp8WJXbbudjMC3N564dNIU5UPerOMBRV4C8Cet/z6llHpXRK4F8H+VUo7Tg4mJCTU3N+fr\neIhoOB4pncYzJ8+G8twZAFfnNVSX6si4WPzV2zFYrSU4faWWkY4cPtC8snjirm2htmAQkVNKqYle\n9/M1hy8imwCMA3gVwMeVUu+2PvUzNFM+RBQDXnvWlMqV0II9AKzgytVDr2CvZaXj+zBexdx+43q8\ncKpi+SZQyGkQaT6Pn318hsm3gC8iVwF4AcBepdS/iEj7c0opJSKWPwUReRDAgwAwNjbm13CIqE9O\nPWusKlK8LoyGzhCJrBZMJ65fhwNHFts7ewt5Dbt/5dqON4KGUu01A7fBPgrn5PqS0hERDcBfAzim\nlPpK67YzYEqHKHYmZ487LnYWDfXq71RrrlIoUVMs5HBiZkfX7aVyBY+9vNi11mCX6rF7HDO719Tt\n1/fiNqUz8E5baU7l/xzAj/Rg33IEwBdb//4igJcGfS4iCl6vyhZ9dqrvwo1bsAfs6/UffvG05cKy\n3XfotjonKufk+tFaYRLAbwPYISLzrf8+B2AWwK+LyI8BfKb1MRFFWKlcgfS+m6teOFFmVVXjtsdP\nr8fxcr9hV/cMnMNXSv0dYPs78ulBH5+IhufgsTO+Ny2LGrv9BL1m2+a0Tq99Ceb9B1pGOjZuhXFO\nLpunEVFbXDYQ9Ws0r9mWUDrNtnNaFg9sH2t30ywWco6lmObmcxeW6oC0Kn1cfH1Q2FqBiNrsWiok\nweqRTMfmLHOJpFVdPgDktQz+yGNwtkoP1RsKa1ePYH7/Tl++n35whk+UAm572w87xTBMl5ZXsPfQ\nPG76g7/B9PMLXa2fAeDuW4td+WnlalWjU1QWac04wyeKMTebeR4pncazJ8+288/GAAd0t09IuqV6\nd6PkWr2BvYfmkRXpWsOo1Rs4cGTR06apsI5M7MX31gqDYB0+kXtWPWNyWhZ331rEK6+dby8WOvWv\nyWYEDdNC4kf1RuIXbgfVq52C3c8mqLz90OrwiWj4SuUK9h1esDyo45mTZzsXCx00TN3DavUG8quy\nNvcmXa9zZ81HJoa1SGvGlA5RzOizx6A2PF28HO8a+2HplY8fZp97tzjDJ4qZfjYIkf/Czsf3gwGf\nKGbCrvSgcDZN+YEpHaKIsqvA6bUQS8Hy0hI5ahjwiSLCGOCvzmm4eHnZ8rDsCBXWpY5f3S3DwoBP\nFAEP/K9/wIk33m9/rPdiN6rVG9h3eCGW3SmTIK5pHCMGfCKEexrRI6XTHcHeCYP9cBULuVBPqPIb\nAz6lXtinET336rnAn4O885q+icIRhr0w4FPqWZU56htrgvqDNQYHztmjyUv6JuxJg1sM+JR6bhtd\nDTKDM/dG//Cj5Y7e6BQto3mt69xep599GJOGfjDgU+q5aXQ1yAzO/LUsqYy+/Xdsbf/bzc8+qt0x\nzbjxilJvetcW5LTO/jHmigynGVwv3BkbLzd8bK3r2bsuKkcY9sIZPqWe/sftdMnudQbHHH205bQs\n1mgZy6utpcud7ZPd/OytDk+JYhknAz4Reje6skv7KACbZo527L60ao1L4ZPWobT6G/pDh+Yt71ep\n1rB55ig2FHK4/cb1yIhYlsMaZ+9uJg1RwH74RC64CeJ6v/MDRxYtN05RuL6wfax9TsCGQg5Ll5f7\nXk8Jsrd9P9z2w2fAJ3JJ70HvtPmpkNMY7CNIAKzRsr5cdWVF8OV7b45MsAd4AAqR76bGi1jpMUFi\nsI8mBfiWYltRKlLB3gsGfCIPolZ1QcMX598BBnwil0rlCpYuL4c9DApRFCtvvGDAJ3JBX7Tlpql4\nGs1rXXst3Mi0vjZK59IOgmWZRC5w81S8XViqYzSvYfVIBtVaHa0KzZ5WAORXjaD86M6ARzgcDPhE\n6N0rxaoGn+LlwlIdWkbw1H23AGi+iVeqtZ7BP2rtEQbBgE+pVipX8NjLix2pGnOvlFK54npGSNFW\nX1HYe2gexdamqldeO49KtYaszeYqIN6LtGYM+JRaTpupjL1S9h1eYLBPmEq1hmdOnm1/3FAKWlYA\nhY4upnFfpDVjwKfU6pWXr1Rr2Guz/Z6Sp95QGM1ryK8aiXR7hEEw4FMqlcoV5uWpS3WpnpgFWiss\ny6TUKZUrmH5+IexhUAQlKV9vhQGfUufAkUWeNkVdkpavt8KUDqUO+92Q2Whew/47tiYqX2+FM3wi\nSr38qpHEB3uAAZ9SaDSvhT0Eipgkba5ywpQOJdojpdN47tVzaCiFrAi2//Jo2EOiCEr6Yq2OAZ9i\np1cbBN0jpdNdm2tOvPH+MIdKMbHpF9MR8H1J6YjIX4jIeyLyj4bb1onIt0Tkx63/c2pFA9N3x1Za\nh4PrbRBK5UrXfZ979dzwB0ixdPInF8IewlD4lcP/SwCfNd02A+A7SqkbAHyn9THRQKx2xxrbIBg5\nHUVIZJSW3xVfAr5S6v8BMF8r3wngq61/fxXAlB/PRelmt7hmdbtI0KOhpMim5JclyCqdjyul3m39\n+2cAPh7gc1FK2C2umW8vlStIyaSNeijktPYhJmtXWR+Ccv8nNw53UCEZyqKtUkqJiOWfn4g8COBB\nABgbGxvGcCjGpndt6epwqWUE1aXL2DRzNMSRURQJgPn9nb1xzJVb939yIx6f2hbOAIcsyID/TyJy\nrVLqXRG5FsB7VndSSj0N4GkAmJiY4JyMHOnVOHqVztU5Df96aRkXL/M0KupmdUX4+NS21AR4syBT\nOkcAfLH17y8CeCnA56KEK5UrmJw9js0zR3Hw2BlM79qCN2d3Y+3qETTYFyeVMoKe59QuXV62rOBK\nK1E+JDpF5DkAnwJwDYB/ArAfQAnAYQBjAH4K4F6llGMR9MTEhJqbmxt4PJQsdgeVrF2V5cw+xb6w\nvZkCNu61sJLTsgMdPu5230eYROSUUmqi1/18Sekope63+dSn/Xh8Sje7g0oY7NPrho+tbR9P2Ite\ntttPkDZPNszHX8YNe+lQZOlpHB5UQmZv/XzJ0+9Fv71yvOz7iAO2VqBI0S+fK9UaDw4nW/WGt9+M\njAhK5YrnWbmXfR9xwIBPoTHnRm+/cT1eOFVpz6gY7MkvDaX6SsVsKOQsryTi2myNKR0KhVVPnGdP\nnnU8VJzIjQysd1n3k4qZ3rWlqxIozidjcYZPgbOqcrDKjXJGT4PKiuDL996Mhw7NW37eayrGvO8j\nqlU6bjHgU6Dsqhw4k6dBrB7J4NLySsdtWkZw8J6bMTVebK8DmfWTipkaL8Y2wJsxpUOBsqtySEuz\nKvJfNiO4Z+I6aFnT75Dhw6SlYvzCgE+BsruEbijVc5ckkZWVFYWjP3i3q1Kn3lDtHP3UeBFP3LUN\nxUIOAqBYyA20+SopmNKhQF2d01Ct1btuL7ZyofsOL6SmFzn5QwG4sNT9OwV0TjCSlIrxC2f4FJhS\nuYKLl5e7btcygttvXI+Dx84w2JOv4louOSyc4ZNvzNU4S5eXLTfI1FcUnvvuOTY9I18xR98bAz75\nwqoaxwmDPQ2qkNOwdvVIIsolh4UBn3xh1+CMKAg5LYsDe7YywHvEHD75Iq69RSi6Jj+xzrKSKyNX\nds2y1703DPjkCy6Wkd/umRjrKK0s5DRoWYGeDdQ38THou8eAT76w2uhC5EQ/WNyO3sP+xMyO9ulm\n5iKAOLcqDgMDPjkyHi04OXvccTa1eoS/TuSOACg/uhMPtE6tsmJOEyatVXEYuGhLtnqd9sPe9dQv\nPQX4+NQ2vHDqbdTqK7b3MX6cpFbFYeCUjGw5nfZjbG8MMNiTe1pWcPHScvuq8e5br3PV94b9cQbH\nGT7ZcrqEZhkm9UNal4J6uw39HASFZmvjhlLtthvmksuktSoOAwM+2XK6hGbelPqhFFA3tdPQP9Ib\n6jkFcfbHGQxTOmTL6RKaeVMKAqtugsWAT7bsWswCwIWLl8IdHMVG0ePkgFePwWFKJ0WsDg1/5bXz\njvlQ8yV0qVzB9PMLqLMXDrlQ7CP9x6vH4DDgp4RVieUzJ8+2P6+XXM799H3HN4GDx84w2JMrWkba\n5xf3aqanY9VNsERFqB/5xMSEmpubC3sYiTQ5e9zVH525nl7LCtauGkG1Vm9XURC5IQCevO8WAHA8\nxzgrghWlWHUzABE5pZSa6HU/zvBTwu1ltTmc1xuqXULHYE9eKACPvbyI8qM7AQB7D81b3m9FKbw5\nu3uII0svLtqmRCGvhT0ESiH9KMKp8aLt4i1z9sPDgJ8CpXIFH37UfdQg0TDo/Ze4UzZ8DPgpwIVW\nCtOBI4sA7Mt8mbMfHubwU4B1zRSmaq2OUrnSLvFlgA8PZ/gx5aVtMXOkFLbHXl4MewgEBvxYeqR0\nGg8dmkelWoNC75N/rHKnTgdPEPXDKZjoi7cULgb8mCmVK+3ugkZOPUiscqdOB08Q9aO7oz1FDQN+\nzBw8dsa297yXXP3E9euwdhWPJKThKORYFhwFXLSNGaegbpertzu5arnBfvbkr0JOw8VLyx1VYVpG\ncGDP1hBHRToG/Jix61EvgG09s93JVUR+ymnZdmDnISXRxIAfM9O7tnT1JREAD2wf6/qjMp45SxQE\nvfeS+ZQqBvhoYsCPGbfHvJnTOERB0IP9iZkdYQ+FXAg84IvIZwH8MYAsgD9TSs0G/ZxJ52bzCs+c\npWHhxr74CDTgi0gWwJ8C+HUAbwP4nogcUUr9MMjnTSPz4SZM49CwcGNffARdlnkbgNeVUj9RSl0G\n8DUAdwb8nKmjp2+MG7GIvMhKcyveqMeuqmx+Fi9BB/wigHOGj99u3dYmIg+KyJyIzJ0/fz7g4SQT\n0zc0CAHwxhOfw1uzu5FfZX/Rr9fS628ObH4WP6Ev2iqlngbwNNA88Srk4cQKq3DID8aUjFM+fn7/\nzmEMhwIU9Ay/AmCj4ePrWrfRgIxpHKJ+mVMydvl4u8NLKF6CDvjfA3CDiGwWkVUAfgvAkYCfMxWY\nxqFBWaVkeEhJsgWa0lFKLYvI7wE4hmZZ5l8opdgndQBM49CgnOrm3e7zoHgKPIevlPomgG8G/Txp\nwM1UNKiM2Lfg0PGQkuRit8wYYRqHBsWTLtONAT9GuKOR/GB3bgIlX+hlmWlm3h3bK1dayGs8OYgG\nxolDejHgh8SuRz1g3WmwVK7gw4+WhzpGSqZCXsPk7HEuyqYQUzohsetRb3e5ffDYmY5DJcy0jEDL\n8qRacqZlBR9+tOz6PGRKFgb8kNhdVnu9XXfVmhHctmkUGcZ8spEVwdpVI10TB6eJBiULA35I7HY0\ner1dd2GpjhNvvM8qDLKU07L48r0344Oa9RoQ8/rpwIAfEq87Gq3uT2RFAEx+Yh2KhRwEnTtq+51Q\nUDJw0TYk/exoXD2SYR0+9aQAvPXzmuVuWqsjMtk6IT1EqejkACYmJtTc3FzYw4gEY8lmIa/hg6U6\nVsIeFMWKAJYTCa/lwBR9InJKKTXR636c4UdMqVzBgSOLqBpyray9p34Yq3AAdBwwzgCfTszhR4he\nm1+1WVgj6gercEjHGf4QuL2EZq8cGoSgOau3wiocAjjDD5zVebN2G134R0n9KhZyeHN2t+1BJazC\nIYABP3BedtTyj5L6IbjS8pgHmJATBvyAedk5a1drv3YV6+/JnkLnguwTd22zrMEnYg4/YBsKOcvT\nqcyzeT3PX6s3kBVBQykUDfn+rY/+LS5eZn4/6YqFHDb9Yg5//8b7tvl4q68xYhUO2eEMP2BuLrHN\nB5I3lGrfR//DZbBPLmn1P9Lf4N/6ec11sGe6hrxgwA+Ym0tsr50zKRlu+NjaZmVNK7rrC/pezite\no/FPmNxjSmcIel1i2+X5K9UaPvHwN3H/JzdCywB1brVNlB+/d7HrNmNKz8poXsOHHy23O15eWKo7\nnqNAZMTpQQQ4Vec0lMIzJ88y2KeIVbDPaVk8dd8tyLO9MQ2AAT8C2AmTnIzmtXYasN/zEogABvxI\n0PP8o3kt7KGQjzLiT0ltftVIO13D9sY0CAb8CNBLMtkkLTlWZQXZjNhWV3k5ktI4e+fGKhoEF21D\nVipXMP31BdQb0WlTTYOrN5RtaaVefgkA+w4v2C7Q6oyz937OUSDSMeCH7EvfOM1gn0BOP1FjgH7o\n0Lzj41jN3rmxivrFlE6ISuUKN1SlkLGixin3zrYI5DcG/BAdOLIY9hAoBG5y8k/ddwtOzOxgsCdf\nMaUzROa++DzoJLlyWhYChSWLDRTMyVNYGPB9ZnfYid4vR2+h4GX7PMVLXsvgj+7aBgCuDgxnTp6G\nhQHfR1ZBXd/2ztOs0mN07equXkmcvVMUMOD7yKkJGndCpofxZ83ZO0UJF2195LTtnTshk8du2xR/\n1hRVDPg+ctr2zp2QyVIs5PDA9jHbXa+lcgWTs8exeeYoJmePW55hTDRsDPg+siqxEzRz+SzBTI5i\nIYcTMzvw+NQ2y7MOALg+uJ5omJjD95GxxK5SrTUPt2h9jiWYyWCusrHK0U/OHrddy2E+n8LEGb7P\npsaLODGzA8VCzvUxdRRdhZzm+UBwtjCmqOIMPyD8406GA3u2ep6Vuz24nmjYBprhi8g9IrIoIisi\nMmH63MMi8rqInBGRXYMNM374x50M/aRg2MKYomrQGf4/ArgLwP803igiNwH4LQBbAWwA8G0R+fdK\nqVjvPNJ30Vaqtfa5o0WbzTTTu7Z07bLUMoKr1oyw731MFPt802a7BIqqgQK+UupHACDSVZF8J4Cv\nKaUuAXhTRF4HcBuAfxjk+cJk3kWr9zCvVGuYfn4Bj728iOpSveuP2/gGUV9R6NH6nCJCy8hAM3Ju\nuKIoCiqHXwRw0vDx263bYsupNUJ9RbVn7eY3gEJeg5aR9sHTrNaJh4P33MyATYnTM+CLyLcB/JLF\np76klHpp0AGIyIMAHgSAsbGxQR8uMF4WYY1vAEzfxE+xkGOwp0TqGfCVUp/p43ErADYaPr6udZvV\n4z8N4GkAmJiYGGrCw66zpRW7yguKFi0jWLt6xPJKqpBrHhKvf27tqiwuL6+0r74ALq5SsgWV0jkC\n4H+LyFfQXLS9AcB3A3quvjh1trQK+laLsBQ9V60Zwf47tnb9rATA52++Fo9Pbeu4v5c3faK4G7Qs\n8zdE5G0AvwrgqIgcAwCl1CKAwwB+COBvAfxu1Cp0nDpbWpkaL7a30QNAtrVQXchp0LJ2bbRo2KpL\ndUyNF3H3rZ1BWwE49L1zHe0NGOwpbQat0vkGgG/YfO4PAfzhII8fpH52Q9pVXhgDx9U5jQuzIdL3\nPxz9wbtdn6s3FB57edH2QBqnKzyiJEhtawWnzpZe6e0U3pzdjQN7tg46NLKQcXERZcy/2y2W67d7\nvcIjSoLUBvwgdkPqs0byV07LYqXHcn5WBHff6r72nf1uKI1SG/CNOXkvjbGc8BhD/2VFUKs32msm\ndhpK4YVTlXaOXq/IMdNv9/MKjyguUt08ze/dkJwd+ktwZUdzw8UWZWML4gN7tmL6+YWOkkstI+2U\nm1XVFUsyKelSHfD9Vshr3Gjlo342Zehvur362bDfDaURA76P2CdnOPTS2F4tiHtdwbHfDaVNanP4\nQfiA5ZiW+tml4PQ171RrbEFM1AcGfINBD55O64JfrzbCD2wf61gcH81bL6hmRdr3eWD7mG3Q39Dq\ndeP3ojtR0jGl0+LHRpy0tl84MbMDk7PHLVMshZzW1c5g88xRy8dZUQpvzu7uuO3Zk2c7cvnGWTxT\nMkTeMOC3OG3E0YOKm634a7RMqgK+Plu3q3o5sGdr1+tmtxvZfIX0+NQ2TFy/jgurRD5hwG/ptRHn\nkdLpjtmm+QrAfIWQFPrJXnaqS3VsnjmKDYUc7r61iFdeO493qjUU8hqUAvYemocAHa+blpWOMwIA\n+/w7Z/FE/mEOv8VpI06pXOlKLQCdW/GTuOkqp2V71r+r1n+Vag2HvnsO07u24Mn7bsFH9ZX2LN78\nCPWGwlVrRph/JxoyzvBbnDbiHDx2xrYmXL8CSNqmq0JOw4E9W9tHNLpRX1E4cGQRa1eP9Hzzqy7V\nUX50px9DJSKXOMNvcar6cArm+pVB0ip01q4ewdR4EdO7tnhq/1yt1V29+SXt9SKKA87wDezyxU6n\nXd1+43oA/lfoCJo7d/VzcZVqBlNjPjxI5h2rj7286HoXca/TwVgvTxSO1AT8QQ67cArmL5yqYOL6\nde3H2nd4wTLv7SVQ57SsZU7brvSxH73Go1rPp79O+lg2zxx1/LrRvGb5eunPVzS99jyEhGh4UhHw\nB62x1+/z0KF524VbY1C0WgtYo2VczZDNAdHIz3WCNVoWd99axNEfvGs7LqvXyWn2rmUF++/Y6rpP\nDQ8hIRquVOTw/TrsotfCLWC/FlB1GexPzOxwPEi9F7fZ9lq9gVdeO4/yozvx1H232O6WNb9OVi0N\ngObM/uBv3tzRnEw/FMbue+IhJETDlYoZvt3MuFKtYXL2uKt0glMQMgdiq7WAXtUubvLavdYJ9KsD\nu7SSmdsrBvMbGuBPl0keQkI0XKkI+HZpCMGVjou90glOwdrNAqSXvLYdpwVU/Q1jaryIhw7N9xwP\ncGWPQa/F5owISuVKx+zdj5SL3c+FFTxEwUhFwHcKtkbmVgq6Urliu8g5mtc8rQM4zYzdLGDqwdbp\nvr2qZIDOPQa9KosaSgWSW7/9xvWOvXKIyF+pCPhWwdYuIFqlE5w2Xu2/w/2h5U4zY68LmE6PNb1r\nC6a/voB6w3rUxvNf3V4N2L0Z9qtUruCFU5WO11UAT+fSEpE3qQj4QHeAtCtxtEonDCOn7KZ5m1u9\nauf1818nrl/n6mpA5+frYPX9KgCvvHbet+cgok6pqNKx4uUADaecsl8VJX4vYE6NF1F+dCfemt1t\nWYGjv5lYvQ5Ofej9wgVbouFLbcD3coCGU07ZrwDl1LxtUE7B1ep1eGD7WOCnSQX5/RKRtUSmdNzu\n3nRbbTI1XsSBI4uuerj3Oxan5m2D6lUNY/U6BN2HPsjvl4isJS7gB7V788CerZ4DlJex+FnfbtZP\ncA26D32Q3y8RWRPlYoPOsExMTKi5uTnPX2ecRWdsDuzQd7EOwmvfF7uFYT/G4hV71hAll4icUkpN\n9Lpf7Gf45lm03Q5TP3LtXme9UVqY5MlRRBT7gO/2pCm3i4F+zoS5k5SIoiT2VTpuZstuFwP1q4VK\ntdY+tu/hF0+jVK70NTYvpZ9EREGLfcC3my1nRTyfl+p390YvpZ9EREGLfUrHrgKln8AaRM6duXMi\niorYz/D9nEVzMxARJVnsZ/iAf7NobgYioiRLRMD3CzcDEVGSMeCbMOdOREkV+xw+ERG5w4BPRJQS\nDPhERCnBgE9ElBIM+EREKRGp9sgich7AT8Meh4VrAPxz2IOICL4WV/C1aOLrcEVYr8X1Sqn1ve4U\nqYAfVSIy56bXdBrwtbiCr0UTX4crov5aMKVDRJQSDPhERCnBgO/O02EPIEL4WlzB16KJr8MVkX4t\nmMMnIkoJzvCJiFKCAd8jEdknIkpErgl7LGEQkYMi8pqI/EBEviEihbDHNGwi8lkROSMir4vITNjj\nCYuIbBSRV0TkhyKyKCK/H/aYwiQiWREpi8hfhz0WOwz4HojIRgA7AZwNeywh+haA/6CU+hUA/x/A\nwyGPZ6h87wQ2AAACAklEQVREJAvgTwH8RwA3AbhfRG4Kd1ShWQawTyl1E4DtAH43xa8FAPw+gB+F\nPQgnDPjePAngvwJI7cKHUur/KKWWWx+eBHBdmOMJwW0AXldK/UQpdRnA1wDcGfKYQqGUelcp9f3W\nv/8VzWCXyt7iInIdgN0A/izssThhwHdJRO4EUFFKLYQ9lgj5zwD+JuxBDFkRwDnDx28jpUHOSEQ2\nARgH8Gq4IwnNU2hOBlfCHogTHoBiICLfBvBLFp/6EoD/jmY6J/GcXgel1Eut+3wJzUv6Z4c5Nooe\nEbkKwAsA9iql/iXs8QybiHwewHtKqVMi8qmwx+OEAd9AKfUZq9tFZBuAzQAWRARopjG+LyK3KaV+\nNsQhDoXd66ATkd8B8HkAn1bpq+utANho+Pi61m2pJCIamsH+WaXUi2GPJySTAPaIyOcArAHw70Tk\nGaXUF0IeVxfW4fdBRN4CMKGUSl3DKBH5LICvAPg1pdT5sMczbCIyguZi9afRDPTfA/CflFKLoQ4s\nBNKc/XwVwPtKqb1hjycKWjP8/6KU+nzYY7HCHD559ScAfgHAt0RkXkT+R9gDGqbWgvXvATiG5iLl\n4TQG+5ZJAL8NYEfrd2G+NculiOIMn4goJTjDJyJKCQZ8IqKUYMAnIkoJBnwiopRgwCciSgkGfCKi\nlGDAJyJKCQZ8IqKU+DfrKN344sRMQAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10847cdd8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(x, y)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def J(theta, X_b, y):\n",
    "    try:\n",
    "        return np.sum((y - X_b.dot(theta)) ** 2) / len(y)\n",
    "    except:\n",
    "        return float('inf')\n",
    "    \n",
    "def dJ(theta, X_b, y):\n",
    "    return X_b.T.dot(X_b.dot(theta) - y) * 2. / len(y)\n",
    "\n",
    "def gradient_descent(X_b, y, initial_theta, eta, n_iters=1e4, epsilon=1e-8):\n",
    "\n",
    "    theta = initial_theta\n",
    "    cur_iter = 0\n",
    "\n",
    "    while cur_iter < n_iters:\n",
    "        gradient = dJ(theta, X_b, y)\n",
    "        last_theta = theta\n",
    "        theta = theta - eta * gradient\n",
    "        if (abs(J(theta, X_b, y) - J(last_theta, X_b, y)) < epsilon):\n",
    "            break\n",
    "\n",
    "        cur_iter += 1\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2.81 s, sys: 134 ms, total: 2.94 s\n",
      "Wall time: 1.88 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "eta = 0.01\n",
    "theta = gradient_descent(X_b, y, initial_theta, eta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3.00383464,  4.01706856])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 随机梯度下降法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dJ_sgd(theta, X_b_i, y_i):\n",
    "    return 2 * X_b_i.T.dot(X_b_i.dot(theta) - y_i)\n",
    "\n",
    "def sgd(X_b, y, initial_theta, n_iters):\n",
    "\n",
    "    t0, t1 = 5, 50\n",
    "    def learning_rate(t):\n",
    "        return t0 / (t + t1)\n",
    "\n",
    "    theta = initial_theta\n",
    "    for cur_iter in range(n_iters):\n",
    "        rand_i = np.random.randint(len(X_b))\n",
    "        gradient = dJ_sgd(theta, X_b[rand_i], y[rand_i])\n",
    "        theta = theta - learning_rate(cur_iter) * gradient\n",
    "\n",
    "    return theta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 559 ms, sys: 22.6 ms, total: 582 ms\n",
      "Wall time: 647 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "X_b = np.hstack([np.ones((len(X), 1)), X])\n",
    "initial_theta = np.zeros(X_b.shape[1])\n",
    "theta = sgd(X_b, y, initial_theta, n_iters=m//3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 3.04732375,  4.03214249])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
